/*
题目：逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 */
import java.util.Stack;
public class EvalRPN {
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        for (String x : tokens) {
            int operation = isOperation(x); //接收相应的返回值
            if (operation == 0) {   //如果不是操作符
                stack.push(x); //入栈
            } else {
                int right = toInt(stack.pop()); //分别是左操作数和右操作数
                int left = toInt(stack.pop());
                int toPush = 0; //接收left和right运算之后的数字
                switch (operation) {
                    case 1 : toPush = left + right;
                        break;
                    case 2 : toPush = left - right;
                        break;
                    case 3 : toPush = left * right;
                        break;
                    case 4 : toPush = left / right;
                        break;
                }
                stack.push(String.valueOf(toPush));
            }
        }
        return toInt(stack.pop());
    }

    //将传进来的字符串转换成整数
    public int toInt(String str) {
        boolean flg = false; //判断正负数
        int n = 0;
        if (str.charAt(0) == '-') {
            flg = true;
            n = 1;
        }
        int len = str.length();
        int ans = 0;
        while (n < len) {
            ans = ans * 10 + str.charAt(n++) - '0';
        }
        ans = flg ? ans * -1 : ans;
        return ans;
    }

    public int isOperation(String str) { //将操作符转化成相应的数字
        if (str.length() > 1)  return 0;
        char ch = str.charAt(0);
        switch (ch) {
            case '+' : return 1;
            case '-' : return 2;
            case '*' : return 3;
            case '/' : return 4;
        }
        return 0;
    }
}
